The present invention relates generally to electronic cryptography technology, and in particular to protecting a security device against side-channel attacks by using multiplicative masking using simultaneous exponentiation techniques.
Electronic communication and commerce can be powerful yet dangerous tools. With the wide-spread availability of network technology, such as the Internet, there is an ever increasing use of online tools for communication and commerce. Every year more users find it easier or quicker to conduct important transactions, whether in the form of correspondence or commerce, using computers and computer networks. However, there is always the risk that the security of electronic transactions is compromised through interception by third parties who do not have the right to partake in the transactions. When malicious third parties obtain access to otherwise private transactions and data there is risk of economic loss, privacy loss, and even loss of physical safety. Cryptography is one mechanism employed to avoid intrusion into the privacy of electronic transactions and data.
Cryptography is a technology for hiding a message in the presence of third parties using mathematical techniques in which a message is encrypted in such a way that it can only be decrypted using a secret key that should only be known by the recipient and/or sender of a message.
Cryptographic algorithms have inputs and outputs. In the case of encryption, the input is a message that is to be protected in plaintext. The plaintext message is manipulated by the cryptographic algorithm to produce a ciphertext, the output. To produce the ciphertext the cryptographic algorithm performs certain mathematical operations that include the use of a secret key. The key may be a shared secret, e.g., between a sender and recipient, or may be a private key held by the recipient.
One frequently used cryptographic technique is the RSA algorithm named for its inventors Rivest, Shamir, and Adelman. To obtain a highly secure ciphertext, the RSA algorithm relies on the difficulty of factoring large integers. A user creates a public key by randomly selecting two large similar-sized prime numbers and multiplies these two numbers together. The result is the public key of the user which the user may publish thereby enabling other entities to encrypt messages for the user. While the public key is public and anyone can encrypt a message with its use, the encrypted message can only be decrypted using the corresponding private key which, in effect, consists of the two prime numbers that were used to generate the public key. It is therefore critical to the security provided by the RSA algorithm that the private keys are kept secret and cannot be discerned by a third party attempting to subvert the secrecy of RSA-encrypted messages.
While the details of the RSA algorithm are beyond this document, for discussion purposes herein the algorithm may be reduced to two complimentary calculations for encryption of a message M into a ciphertext C and the decryption of the ciphertext C back into the message M. The public key is computed from two large prime numbers p and q. From p and q a number n=pq is computed; n is the modulus for both private and public keys. Furthermore e, the public key exponent is computed from p and q, as follows:
Choose e such that: 1<e<φ(n) and the greatest common divisor of (e, φ(n))=1, i.e., e and φ(n) are coprime, wherein, n=pq and φ(n) is Euler's Totient function.
Thus, the public key consists of the pair of integers (n, e). The corresponding private key consists of the pair of integers (n, d) where d≡e−1 (mod φ(n)) where φ(n) is Euler's Totient function.
A message M is encrypted using the public key (n, e) into ciphertext C by:C=Me mod n
The message M is recovered and decrypted from C using the corresponding private key (n,d) by:M=Cd(mod n)
RSA may also be used to cryptographically sign a message M into a signed message S, i.e.,S=Md(mod n)
Usually these computations are not performed directly as the exponentiations on large integers are expensive computations. A more efficient computation, which involves exponentiation of much smaller integers, uses the Chinese Remainder Theorem. Without going into details, the Chinese Remainder Theorem approach includes the modular exponentiations:Sp=Mpdp mod pSq=Mqdp mod q                Wherein dp=d mod (p−1) and dq=d mod (q−1), and Mp=M mod p and Mq=M mod q        
The RSA-CRT signature computation is composed of 3 main steps:                Computing Sp (about 45% of the computation)        Computing Sq (about 45% of the computation)        Recombining S from Sp and Sq (about 10% of the computation)        
Side-channel attacks make use of the program timing, power consumption and/or the electronic emanation of a device that performs a cryptographic computation. The behavior of the device (timing, power consumption and electronic emanation) varies and depends directly on the program and on the data manipulated in the cryptographic algorithm. An attacker could take advantage of these variations to infer sensitive data leading to the recovery of a private key.
Fault attacks derive their name from the practice of creating a fault during the computation and exploiting the result produced by that fault to deduce the secret key. Generally, injecting a fault requires a prior step that consists of determining the most likely successful moment for the fault injection. This prior step is usually done by reverse engineering the program through studying the power or the electronic emanation trace. RSA-CRT is particularly vulnerable to fault attacks because disturbing either the computation of Sp only or Sq only can allow the intruder to deduce the private key, whichever fault effect is caused. Moreover, the set up for inducing a fault during either Sp or Sq computation is relatively easy to do because these two sensitive steps are usually easily identifiable on a power trace. Since Sp and Sq occupy a large portion of the process, roughly 45% each of the total signature, there is ample time to disturb either computation. Thus, a fault disturbing the computation of either Sp or Sq could allow the unauthorized recovery of the private key prime factors.
One mechanism used to defend against fault attacks is to perform the signature operation twice to ensure that no fault has been introduced during the computation. Doing such operations twice would be a costly countermeasure.
Other prior art techniques include Shamir (Shamir, U.S. Pat. No. 5,991,414, Method and apparatus for protecting public key schemes from timing and fault attacks), Aumuller (Aumuller et al, Concrete results and practical countermeasures, Cryptographic Hardware and Embedded Systems——CHES 2002: 4th International Workshop, Volume 4), Giraud (Giraud, C., An RSA implementation resistant to fault attacks and to simple power analysis, IEEE Transactions on Computers (Volume: 55, Issue: 9), September 2006), and Vigilant (Cryptographic Hardware and Embedded Systems—CHES 2008, Lecture Notes in Computer Science Volume 5154, 2008, pp 130-145).
These prior art techniques may be divided in two types:                The Shamir technique, from which the Aumuller and Vigilant techniques are derived, consists of multiplying the modulus by a small random number before the exponentiation. The exponentiation is performed modulo this new number and some consistency checks can be performed modulo the small random number after the exponentiation. A global consistency check is performed after the recombination. If the global consistency check fails, a fault attack may have been detected.        Giraud's technique consists of using the Montgomery ladder exponentiation algorithm that outputs (X(y−1) mod Z, Xy mod Z) when computing Xy mod Z.        
Common to these prior techniques is that they all detect the fault with some probability, except Giraud's one. But Giraud's technique has the drawback to require a large amount of RAM memory for its implementation. Moreover these techniques keep a three-step structure: computation of Sp, computation of Sq, and recombination. Having three steps provides an attacker multiple opportunities to set up a fault attack.
From the foregoing it will be apparent that there is still a need for an improved technology to provide a secure mechanism that is computationally efficient, that does not require excessively large registers or other storage, and in which a portable security device—e.g., a smart card connected to a host computer—can provide the capability of providing cryptographic services that are protected from fault attacks.